package array

import "math"

// https://leetcode-cn.com/problems/degree-of-an-array/
// 直接遍历，但是注意出现次数要记录起来，因为有可能有几个数字出现的次数都一样，但是有一个最优解
// 时间复杂度: O(n)
func FindShortestSubArray(nums []int) int {
	numOccurCountMap := make([]int, 50000)
	numStartPos := make([]int, 50000)
	numEndPos := make([]int, 50000)
	for index, currentNum := range nums {
		numOccurCountMap[currentNum]++
		if currentNum == nums[0] || numStartPos[currentNum] != 0 {
			numEndPos[currentNum] = index
		} else {
			numStartPos[currentNum] = index
			numEndPos[currentNum] = index
		}
	}

	maxOccurCount := 0
	for _, currentOccurCount := range numOccurCountMap {
		if currentOccurCount > maxOccurCount {
			maxOccurCount = currentOccurCount
		}
	}

	minSubArrLen := math.MaxInt16
	for currentNum, currentOccurCount := range numOccurCountMap {
		if currentOccurCount == maxOccurCount {
			currentLen := numEndPos[currentNum] - numStartPos[currentNum] + 1
			if currentLen < minSubArrLen {
				minSubArrLen = currentLen
			}
		}
	}
	return minSubArrLen
}
